{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "d8594bbb",
   "metadata": {},
   "source": [
    "## 链表相交\n",
    "[链表相交](https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/)\n",
    "\n",
    "关键在于链表对齐后再进行同步移动和值的判断。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "106b186d",
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import Optional\n",
    "class ListNode:\n",
    "    def __init__(self,val:int =0, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getIntersectionNode(self,headA:ListNode,headB:ListNode) -> Optional[ListNode]:\n",
    "\n",
    "        lenA = self.getLength(headA)\n",
    "        lenB = self.getLength(headB)\n",
    "\n",
    "        if lenA > lenB:\n",
    "            headA = self.moveForward(headA, lenA - lenB)\n",
    "        else:\n",
    "            headB = self.moveForward(headB,lenB - lenA)\n",
    "\n",
    "\n",
    "        while headA and headB:\n",
    "            if headA == headB:  # 这里比较的是对应的指针\n",
    "                return headA\n",
    "            headA = headA.next\n",
    "            headB = headB.next\n",
    "\n",
    "        return None\n",
    "\n",
    "    def getLength(self, head:ListNode) -> int:\n",
    "        length = 0\n",
    "        while head:\n",
    "            length +=1\n",
    "            head = head.next\n",
    "        return length\n",
    "\n",
    "    def moveForward(self,head: ListNode,steps: int) -> ListNode:\n",
    "        while steps > 0:\n",
    "            head = head.next\n",
    "            steps -= 1\n",
    "        return head\n",
    "\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "env_py38",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python",
   "version": "3.8.18"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
